package fun.coding.leetcode;

public class ContainerWithMostWater {

	public static void main(String[] args) {

	}
	
	// Keep a two pointer, always move the short one, since x is shrinking, and moving the other side won't help 
	public int maxArea(int[] height) {
		if (height == null || height.length <= 1) return 0;
		
		// Minor, for those obvious two pointer, give it a better name, left, right or (l,r) instead of i, j
		int left = 0;
		int right = height.length - 1;
		int max = Integer.MIN_VALUE;
				
		while (left < right) {
			int area = Math.min(height[left], height[right]) * (right - left);
			max = Math.max(max, area);
			
			if (height[left] > height[right]) {
				right--;
			} else {
				left++;
			}
		}
		
		return max;
	}
	
	/* Naive O(N^2)
	public int maxArea(int[] height) {
		if (height == null || height.length == 0) return 0;
		
		int len = height.length;
		int max = Integer.MIN_VALUE;
		
		for (int i = 0; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				int area = Math.min(height[i], height[j]) * (j - i);
				max = Math.max(area, max);
			}
		}
		
		return max;
	}
	*/
}
